package com.arron.algorithm.leetcodetop100.贪心;

/**
 * @Classname CutRope
 * @Date 2020/9/13 14:31
 * @Created by 刘
 * 剪绳子，给你一根长为n的绳子，然后把绳子剪成m段，然后得到的每段的长度，(n,m都是整数)
 *  求每段绳子的长度的乘积的最大值？
 *      输入n,(2=< n <=60)
 *  解决方法：
 *  1.动态规划
 *  2,贪心算法：
 *      1），每次选择最优，经公式推导得出，当绳子的长度n<5的时候,得到的乘积都是<=n的
 *      3），要使乘积最大，应该使用2和3的组合
 *      2），应该尽量让3出现的次数越多，那么乘积就越大
 *          n==2的时候 输出 1 （剪一刀）
 *          n==3的时候 输出 2（不能一刀都不剪）
 *          n==4的时候 输出 4 （剪一刀）
 *          n==5的时候 输出 6
 */
public class CutRope {

    public static void main(String[] args) {


        System.out.println(maxCutRope(8));

    }

    /**
     * n 输入的绳子的长度
     * 返回绳子的最大乘积
     * @return
     */
    public static int maxCutRope(int n){

        //判断绳子的长度的特殊情况
        if (n == 2){
            return 1;
        }
        if (n==3){
            return 2;
        }
        if (n==4){
            return n;
        }

        //计算出能剪出多少个3,每次剪的时候，尽量让3的次数最多
        int time3 = n/3;
        if (n%3 == 1){
            //如果余数为1，则3的次数减一
            time3-=1;
        }

        //计算2的剪的次数
        int time2 = (n-time3*3)/2;

        //最后直接返回3的time3次方与2的time2次方的乘积,即是绳子剪出来的最大乘积
        return (int) Math.pow(3,time3) * (int)Math.pow(2,time2);
    }

}
